We initiate a thorough study of \emph{distributed property testing} --producing algorithms for the approximation problems of property testing in theCONGEST model. In particular, for the so-called \emph{dense} testing model weemulate sequential tests for nearly all graph properties having $1$-sidedtests, while in the \emph{sparse} and \emph{general} models we obtain fastertests for triangle-freeness and bipartiteness respectively. In most cases, aided by parallelism, the distributed algorithms have a muchshorter running time as compared to their counterparts from the sequentialquerying model of traditional property testing. The simplest property testingalgorithms allow a relatively smooth transitioning to the distributed model.For the more complex tasks we develop new machinery that is of independentinterest. This includes a method for distributed maintenance of multiple randomwalks.
展开▼
